Münchhausen の trilemma
根據關係は以下の三つの少なくとも一つの形を取る
循環論法 (circular argument)。惡循環 無限後退 (regressive argument)
無根據な斷定 (dogmatic argument)
數理的定式化
事の集合$ V:=\{a,b,\dots\}を考へる 「事」の意味は meta 的に與へる
命題・命令・事件等
$ Vは有限集合あるいは可算集合である
二項關係$ \larr_{\subseteq V\times V}を考へる。$ a\larr bを「事$ bは事$ aに基附く」と讀む 「基附く」の意味は meta 的に與へる
被演繹・歸納・解釋・正當化等
頂點の集合$ V、邊の集合$ E=\{a\larr b|a,b\in V\}\subseteq V\times V、寫像$ \larr:E\to V\times V,a\larr b\mapsto(a,b)の組$ G:=(V,E,\larr) $ Gは以下のいずれかを必ず滿たす
循環論法。$ Gは可算長かもしれない閉道$ a_0\larr\dots\larr a_1\larr a_0を含む
可算長の場合は無限後退と考へ、有限長の場合のみを循環論法と呼んでもよい
無限後退。$ Gは可算長の道$ a_\omega\larr\dots\larr a_1\larr a_0を含む
無根據な斷定。沈點が存在する$ \exist b(\neg\exist a(a\larr b))
$ Gが有限の場合に、循環論法もしくは無根據な斷定のどちらかが存在することを示す
沈點が存在すれば、無根據な斷定が存在する
沈點が存在しなければ、
全ての頂點の出次數は$ 1以上である
$ Vの濃度を$ nとする
適當な頂點を$ v_0として選ぶ
$ v_0の出次數は$ 1以上である爲、隣接する頂點を適當に選んで步道$ v_1\larr v_0を構成できる。$ v_1以降からも同樣に步道を構成し、$ \dots\larr v_1\larr v_0とできる。これには切りがない
步道の長さを$ n+1迄延ばす$ v_n\larr\dots\larr v_0。この步道には頂點が$ n+1囘表れる。$ Gには頂點が$ n個しかない爲、鳩の巢原理よりこの步道は少なくとも同じ頂點を$ 2つ含む。これは閉道の存在を意味し、循環論法が存在する $ Gが可算の場合に示す
沈點が存在すれば、無根據な斷定が存在する
沈點が存在しなければ、
任意の頂點$ bに對して集合$ \{a|a\larr b\}は空集合でない 任意の頂點$ v_0から、步道を再歸的に定義する
$ v_{n+1}=f(v_n),$ n\in\N
任意の$ v_nに對して$ v_{n+1}は必ず存在する
或る$ i,j\in\N,$ i<jに於いて$ v_i=v_jであれば、步道$ v_j\larr\dots\larr v_iは閉道であり、循環論法が存在する
その樣な$ i,jが存在しない$ v_{n+1}\notin\{v_n,\dots,v_0\}ならば、步道$ \dots\larr v_0は無限列であり、無限後退が存在する
$ Gが有限の場合に、循環論法もしくは無根據な斷定のどちらかが存在することを代數的に示す
$ V=\{v_1,\dots,v_n\}
$ Aは非負行列である$ A_{ij}\ge 0
沈點が存在すれば$ D_{ii}=0、無根據な斷定が存在する
沈點が存在しなければ$ D_{ii}>0、
$ 0<k\le nとして、隣接行列の冪$ A^kの對角成分$ (A^k)_{ii}に正の成分が存在する、卽ち蹟 (trace)が$ {\rm tr}({A^k})>0であれば長さ$ kの閉道が存在し、循環論法が存在する $ \rho(A)>0であるから、$ {\rm tr}(A^k)>0となる$ 0<k\le nが存在する
邊に label を附與して「基附く」を二種類に增やす
以下は循環論法を持つ
code:mmd
flowchart LR
a --B--> b
b --B--> a
同じ label を持つ邊のみに道を制限すれば、以下は循環論法を持たない
code:mmd
flowchart LR
a--B-->b
b--B'-->a
同じ label の邊が無限に連なる場合を無限後退と呼び、同じ lebal の邊の閉道を循環論法と呼び、label は異なってゐても出次數が 0 である頂點を無根據な斷定と呼ぶとする
道が可算長でも、同じ label の道が有限長ならば無限後退でない$ \dots\xleftarrow{B}v_m\xleftarrow{B'}\dots v_{n+1}\xleftarrow{B'}v_n\xleftarrow{B}\dots\xleftarrow{B}v_0
異なる label の邊による閉道は循環論法でない
code:mmd
flowchart LR
a--B-->b
b--B'-->a
同じ lebel による出次數が 0 でも、異なる label による出次數が正ならば無根據な斷定でない$ \dots\xleftarrow{B'}b\xleftarrow{B}a
code:mmd
flowchart LR
a--B-->b
b--B'-->a
が自明な例である
我々は頻繁にこれをやってゐる
別の理屈を持ち出す
別の分野に預ける
無限後退は無限の廣さの空閒が要る事が問題だと考へる。無限長の道を Cauchy 列に對應させる樣に埋め込めれば、有限の廣さの空閒で無限後退を納められ、問題ではなくなる 循環論法に見えるが、少しづつズレてゐる幾何學的な像を描く事もできる。これは無限後退である
ズレてゐる「循環」の各周囘を同一視して本當の循環論法と見做す事もできよう
事の全體が豫め與へられてゐる (論理的全知。閉包原理 (closure principle)) とは考へず、今檢討してゐる事のみが graph (構造) に載ってゐるとする 非單調論理の樣に、追加した事だけでなく既存の事も變化すると考へてもよい 既存の事を忘卻してもよい
無限後退の價値も、無根據な斷定の價値も變はろう
Claud Sonnet 4
失礼しました。グラフの代数的性質を利用した証明を提示いたします。
**代数的証明:**
$ D の対角成分がすべて正の場合を考えます。即ち、すべての頂点の出次数が1以上です。
**キーとなる代数的観察:**
隣接行列 $ A の固有値を $ \lambda_1, \lambda_2, \ldots, \lambda_n とします。
**補題:** $ D の対角成分がすべて正の場合、$ A のspectral 半徑（最大固有値の絶対値）$ \rho(A) \geq 1 です。 **補題の証明:**
各行の非負成分の和（出次数）が1以上であることから、Гершгорина の定理により、少なくとも一つの固有値 $ \lambda が $ |\lambda| \geq 1 を満たします。 **主証明:**
$ \rho(A) \geq 1 であるとき、以下が成り立ちます：
$ \lim_{k \to \infty} \frac{1}{k} \log \text{tr}(A^k) = \log \rho(A) \geq 0
これは $ k が十分大きいとき $ \text{tr}(A^k) が指数的に増大することを意味します。
$ A が非負行列であり、各行和が1以上の場合：
1. $ \rho(A) \geq 1
2. $ \rho(A) = 1 ならば、$ A は周期的構造を持つ
3. いずれの場合も、ある $ k \leq n に対して $ \text{tr}(A^k) > 0
**代替的な純代数的アプローチ:**
$ p(A) = 0
$ D の対角成分がすべて正の場合、グラフが強連結でなくても、各成分内で閉道が存在するか、成分間の構造により必ず閉道が形成されます。
**決定的論証:**
$ \text{tr}(A^k) = \sum_{i=1}^n \lambda_i^k であり、$ \rho(A) \geq 1 のとき、Newton の恆等式と対称多項式の理論により、有限個の $ k に対して必ず $ \text{tr}(A^k) > 0 となります。 具体的には、$ k \leq n の範囲で $ \text{tr}(A^k) > 0 となる $ k が存在することが、線形代数の基本定理から導かれます。
したがって、$ D の対角成分がすべて正の場合、必ず閉道が存在します。 □
Gemini 2.5 Pro
はい、承知いたしました。「全ての頂点の出次数が1以上の場合に閉路が存在する」という部分について、グラフの隣接行列のspectral 半徑（最大固有値の絶対値）を用いた代数的な証明を試みます。 ---
## 証明（代数的性質を利用）
与えられた主張：有限な有向グラフ G=(V,E,←) は、沈点（出次数が0の頂点）を持つか、あるいは閉道（サイクル）を持つ。
証明：
出次数のみを考えた次数行列を D とし、隣接行列を A とします。$ |V|=n とします。
### 場合1: D の対角成分に 0 が存在する場合
ある頂点 $ v \in V について、$ D_{vv} = 0 であるとします。これは、頂点 $ v の出次数が 0 であることを意味します。したがって、$ v は沈点です。この場合、主張は成り立ちます。
---
### 場合2: D の対角成分に 0 が存在しない場合
全ての頂点 $ v \in V について、$ D_{vv} > 0 であるとします。これは、全ての頂点の出次数 $ d_{out}(v) が少なくとも 1 であることを意味します。このとき、グラフ G が閉道（サイクル）を持つことを、隣接行列 A の代数的な性質を用いて示します。
隣接行列 $ A は非負行列（全ての成分が0以上）です。
ここで、全ての成分が 1 である $ n次元ベクトルを $ \mathbf{1} とします。
$ A\mathbf{1} という積を考えると、その $ i番目の成分 $ (A\mathbf{1})_i は次のようになります。
$ (A\mathbf{1})_i = \sum_{j=1}^{n} A_{ij} \cdot 1 = \sum_{j=1}^{n} A_{ij}
これは、頂点 $ i の出次数 $ d_{out}(i) に他なりません。
仮定より、全ての頂点の出次数は 1 以上なので、$ d_{out}(i) \ge 1 for all $ i = 1, \ldots, n.
したがって、ベクトルとして $ A\mathbf{1} \ge \mathbf{1} が成り立ちます（各成分ごとに比較）。
非負行列の理論によれば、非負行列 $ A と正のベクトル $ x (全ての成分が正) および正のスカラー $ \gamma に対して、$ Ax \ge \gamma x が成り立つならば、$ A のspectral 半徑$ \rho(A) (固有値の絶対値の最大値) は $ \rho(A) \ge \gamma を満たします。（この場合、$ x=\mathbf{1}, $ \gamma=1 とみなせます。） よって、$ \rho(A) \ge 1 が結論付けられます。
次に、グラフ G に閉路が存在しないと仮定します（背理法）。
DAGの重要な性質として、その頂点をトポロジカルソート（ある辺 $ (u,v) が存在すれば必ず $ u が $ v より前に来るように頂点を一列に並べること）が可能です。
このトポロジカル順序に従って隣接行列 $ A の行と列を並べ替えると（これは行列の相似変換に相当し、固有値を変えません）、$ A は真の上三角行列になります。つまり、対角成分およびそれより下の成分が全て 0 の行列となります。
$ A' = P^{-1}AP （$ Pは置換行列）とすると、$ A' は真の上三角行列です。
真の上三角行列の固有値は、その対角成分に等しく、この場合は全て 0 です。
したがって、$ A' の固有値は全て 0 であり、そのspectral 半徑は $ \rho(A') = 0 です。 固有値は相似変換で不変なので、元の隣接行列 $ A の固有値も全て 0 であり、$ \rho(A) = 0 となります。
3. **矛盾と結論:**
ステップ1では、全ての頂点の出次数が 1 以上であるという仮定から $ \rho(A) \ge 1 を導きました。
ステップ2では、グラフに閉路が存在しないという仮定から $ \rho(A) = 0 を導きました。
これら二つの結論 $ \rho(A) \ge 1 と $ \rho(A) = 0 は明らかに矛盾します。
この矛盾は、背理法の仮定「グラフ G に閉路が存在しない」が誤りであったことを意味します。
したがって、グラフ G は必ず閉道（サイクル）を持たなければなりません。
---
以上のことから、D の対角成分に 0 が存在しない場合にはグラフは閉道を必ず持つことが、隣接行列のspectral 半徑という代数的な性質を用いて示されました。 場合1と場合2を合わせることで、元の主張「有限な有向グラフ G は、沈点を持つか、あるいは閉道を持つ」が証明されます。
ChatGPT o4-mini-high
以下、「有限有向グラフ $ G=(V,E,\larr) で出次数に 0 がなく（すなわち sink がない）ならば必ず閉路が存在する」ことを、次数行列 D・隣接行列 A を用いて代数的に完結に示します。
⸻
1. 設定と目的
• 頂点集合 V の濃度を $ \lvert V\rvert = n とする。
• 出次数のみを考えた 次数行列（出次数行列）を
$ D \;=\; \mathrm{diag}(d_1,\,d_2,\,\dots,\,d_n),\quad d_i = \deg^+(i) = \#\{\,j\in V \mid i\larr j\,\}.
• 隣接行列（接続行列）を
$ A = (\,a_{ij}\,){1\le i,j\le n},\quad a{ij} =\begin{cases}1, & i\larr j\ (\text{頂点 }i\text{ から }j\text{ へ辺あり}),\\0, & \text{それ以外}.\end{cases}
このとき、明らかに
$ d_i \;=\; \sum_{j=1}^n a_{ij},\quad A\mathbf{1} \;=\; D\,\mathbf{1},\quad A_{ii}=0\quad (\forall i)
となる（$ \mathbf{1}=(1,1,\dots,1)^\top は全１ベクトル）。
• 命題：
D の対角成分（つまり出次数）に 0 が一つでもあれば sink がある。
したがって、sink がない（$ \forall i,\;d_i>0）場合には、必ず閉路（サイクル）が存在する。
ここでは「閉路がある」ことを、ある長さ 1<k\le n の閉道が存在する、すなわち $ (A^k){ii}>0 となる i があることで示します。なぜなら、$ (A^k){ii} は「頂点 i から出発して長さ k の道をたどり、再度 i に戻る (閉道) パスの本数」を表すからです。特に
$ \operatorname{tr}(A^k)\;=\;\sum_{i=1}^n (A^k)_{ii}
が正であれば（$ \operatorname{tr}(A^k)>0 であれば）、長さ k の閉路が少なくとも１つ存在することになります。
⸻
2. 「sink がない」なら閉路があることの証明
以下、背理法的に示します。
1. 仮定
$ \text{「sink がない」\(\iff\) \(\forall\,i,\ d_i>0\).}
すなわち、行列 D の対角成分に 0 は一切なく、以下が成り立つ：
$ D\mathbf{1} \;>\; 0\quad\Longrightarrow\quad A\mathbf{1} = D\mathbf{1} \;>\; 0,\quad\bigl(\text{すべての行の和が }1\text{ 以上}\bigr).
このとき、少なくともすべての i について
$ \sum_{j=1}^n a_{ij} \;=\; d_i \;\ge1
が成り立っている。
2. 目的
仮に「$ \forall\,k=1,2,\dots,n について $ \operatorname{tr}(A^k)=0」とすると矛盾を導く。したがって、少なくともある $ 1\le k\le n で
$ \operatorname{tr}(A^k) > 0
となり、その k 長さの閉路が存在することが従う。
3. 背理仮定と固有値への帰着
仮に
$ \operatorname{tr}(A^k) = 0\quad (\forall\,1\le k \le n)
が成立すると仮定する。ここで、A の固有値を $ \lambda_1,\lambda_2,\dots,\lambda_n とするなら、一般に
$ \operatorname{tr}(A^k) \;=\; \sum_{i=1}^n \lambda_i^k.
したがって、$ \forall\,1\le k\le n,\ \sum_{i=1}^n \lambda_i^k = 0 となる。これは「次数分だけの冪和 (power sum) がすべて 0」という条件であり、Newton の恆等式（Newton’s identities） によって、次が従う： • $ e_1 = \sum_i \lambda_i = 0
• $ e_2 = \sum_{i<j} \lambda_i \lambda_j = 0
• $ \dots
• $ e_{n} = \prod_{i=1}^n \lambda_i = 0
ここで $ e_k は「固有値の k 次対称式」です。特に最上位の対称式 $ e_n=\lambda_1\lambda_2\cdots\lambda_n=0 であることから、少なくとも１つの $ \lambda_i=0 とは言えます。しかし、より強く帰結するのは次の事実です：
$ \sum_{i}\lambda_i^k =0 が k=1,2,\dots,n すべてで成り立つならば、すべての固有値 $ \lambda_i=0 である。
つまり、A の特性多項式は $ \chi_A(t)=t^n であり、A は nilpotent（冪零）行列になる。
言い換えれば、$ \operatorname{tr}(A)=0,\ \operatorname{tr}(A^2)=0,\dots,\operatorname{tr}(A^n)=0 が一斉に成り立つとき、A の固有値はすべて 0 なので、
$ A^n = 0\quad (\text{零行列}).
4. nilpotent であることの矛盾
いま「sink がない」仮定のもとでは、隣接行列 A の各行和は常に正整数（$ \ge1）である。
• 主張：A が「すべての行和 $ \ge1」を満たすなら、任意の正整数 k について、$ A^k の各行和も必ず $ \ge1 となる。
• 証明（帰納）：
1. k=1 のとき、行和が $ \sum_j a_{ij}=d_i\ge1 なので成り立つ。
2. $ A^k の各行和が全て $ \ge1 だと仮定すると、$ (A^{k+1}){i\bullet} = \sum{j=1}^n (A^k){ij}\,(\text{行 }j\text{ の }A\text{ 行和}) より、
$ (\text{行 }i\text{ の }A^{\,k+1}\text{ 行和}) = \sum{j=1}^n (A^k){ij}\,\bigl(\sum{\ell=1}^n a_{j\ell}\bigr).
ここで、$ (A^k){ij}\ge0、かつ $ \sum{\ell} a_{j\ell}\ge1（全行和 $ \ge1）だから、
$ \sum_{j=1}^n (A^k){ij}\,\bigl(\sum{\ell} a_{j\ell}\bigr)\;\ge\; \sum_{j=1}^n (A^k)_{ij} = (\text{行 }i\text{ の }A^k\text{ 行和}) \;\ge\; 1.
よって $ A^{\,k+1} の各行和も $ \ge1 となる。
3. 以上により、任意の $ k\ge1 に対して「$ A^k の各行和 $ \ge1」が成り立つ。
特に k=n のとき、$ A^n の各行和は $ \ge1 なので、$ A^n は零行列にはなり得ない（少なくともどこか非ゼロ成分を持つ）。
しかし、先のステップ 3 で得た「$ \sum_{i=1}^n \lambda_i^k = 0\ (\forall\,1\le k\le n) ならば $ A^n=0」という帰結と衝突する。
したがって、「$ \forall\,k=1,\dots,n,\ \operatorname{tr}(A^k)=0」と仮定すると矛盾が生じ、いずれかの k（ただし $ 1\le k\le n）で
$ \operatorname{tr}(A^k)\;>\;0
となることが分かる。
5. 閉路の存在
$ \operatorname{tr}(A^k)>0 であるならば、$ \sum_{i=1}^n (A^k){ii}>0 であるから、少なくともある頂点 i について $ (A^k){ii}\ge1 が成り立つ。
これは「頂点 i から出発して長さ k の道をたどり、再度 i に戻る経路が少なくとも１本ある」ことを意味し、まさに長さ k の閉道（サイクル）の存在を保証する。
⸻
3. まとめ
1. もし D の対角成分に 0 があれば、それがすなわち「出次数 0 の頂点＝sink」の存在を意味する。
2. もし D の対角成分に 0 がなければ（sink がないなら）、隣接行列 A は各行和 $ \ge1 を満たす。
• そのとき、$ \forall\,1\le k\le n,\;A^k の各行和も $ \ge1 となる。
• これにより A が「$ \forall\,k,\ \operatorname{tr}(A^k)=0」であることは矛盾するため、必ずある $ 1\le k\le n で $ \operatorname{tr}(A^k)>0 となる。
• 従って、その k に対応して長さ k の閉路（サイクル）が存在する。
したがって、有限有向グラフ G には必ず「sink がある」か「（長さ \le n の）閉路がある」 ことが代数的に示されました。これで証明は完了です。